
/*-------------------------------------------------------------------------
 *
 * gistbuild.c
 *	  GiST索引实现的构建算法。
 *
 * 有两种不同的策略：
 *
 * 1. 对所有输入元组进行排序，将它们按排序顺序打包到GiST叶页面中，并在此过程中创建下行链接和内部页面。这从底部开始构建索引，类似于B树索引构建的工作方式。
 *
 * 2. 从一个空的索引开始，逐个插入所有元组。
 *
 * 如果所有列的操作符类都有定义的'sortsupport'，则使用排序方法。否则，我们将采用第二种策略。
 *
 * 第二种策略可以选择性地在树的不同层次使用缓冲区以减少I/O，详见README中的“缓冲构建算法”以获取更详细的说明。它最初多次调用插入，但在达到一定数量的元组后（除非禁用缓冲模式），则切换到缓冲算法。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/access/gist/gistbuild.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include <math.h>

#include "access/genam.h"
#include "access/gist_private.h"
#include "access/gistxlog.h"
#include "access/tableam.h"
#include "access/xloginsert.h"
#include "catalog/index.h"
#include "miscadmin.h"
#include "optimizer/optimizer.h"
#include "storage/bufmgr.h"
#include "storage/smgr.h"
#include "utils/memutils.h"
#include "utils/rel.h"
#include "utils/tuplesort.h"

/* 索引元组切换到缓冲构建模式的步骤 */
#define BUFFERING_MODE_SWITCH_CHECK_STEP 256

/*
 * 在缓冲模式被显式开启时，以缓慢的方式处理的元组数量
 *，然后切换到缓冲模式。此外，在缓冲模式下，
 * 在重新调整缓冲区大小参数之间处理的元组数量。
 */
#define BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET 4096

/*
 * 用于构建索引的策略。它可以在
 * GIST_BUFFERING_* 模式之间动态切换，但如果使用
 * 排序方法，则需要提前决定，之后无法更改。
 */
typedef enum
{
	GIST_SORTED_BUILD,			/* 通过排序自下而上构建 */
	GIST_BUFFERING_DISABLED,	/* 在常规构建模式中，并且不打算
								 * 切换 */
	GIST_BUFFERING_AUTO,		/* 在常规构建模式中，但如果索引变得太
								 * 大，将切换到缓冲构建模式 */
	GIST_BUFFERING_STATS,		/* 在切换到缓冲构建模式之前
								 * 收集索引元组大小的统计信息 */
	GIST_BUFFERING_ACTIVE		/* 在缓冲构建模式中 */
} GistBuildMode;

/* gistbuild及其回调的工作状态 */
typedef struct
{
	Relation	indexrel;
	Relation	heaprel;
	GISTSTATE  *giststate;

	Size		freespace;		/* 在页面上留出的空闲空间量 */

	GistBuildMode buildMode;

	int64		indtuples;		/* 被索引的元组数量 */

	/*
	 * 在缓冲构建期间使用的额外数据结构。'gfbb'包含
	 * 与管理构建缓冲区相关的信息。'parentMap'是每个内部页面
	 * 的父项查找表。
	 */
	int64		indtuplesSize;	/* 所有被索引元组的总大小 */
	GISTBuildBuffers *gfbb;
	HTAB	   *parentMap;

	/*
	 * 在排序构建期间使用的额外数据结构。
	 */
	Tuplesortstate *sortstate;	/* tuplesort.c的状态数据 */

	BlockNumber pages_allocated;
	BlockNumber pages_written;

	int			ready_num_pages;
	BlockNumber ready_blknos[XLR_MAX_BLOCK_ID];
	Page		ready_pages[XLR_MAX_BLOCK_ID];
} GISTBuildState;

#define GIST_SORTED_BUILD_PAGE_NUM 4

/*
 * 在排序构建中，我们使用这些结构的堆栈，每个级别一个，
 * 用于保存该级别的最后页面的内存缓冲区。
 *
 * 排序GiST构建需要良好的排序操作类线性化。这在
 * 多维数据中并不总是如此。为了解决这些异常，
 * 我们缓冲索引元组并应用可以感知多维度的picksplit。
 */
typedef struct GistSortedBuildLevelState
{
	int			current_page;
	BlockNumber last_blkno;
	struct GistSortedBuildLevelState *parent;	/* 上层级别（如果有） */
	Page		pages[GIST_SORTED_BUILD_PAGE_NUM];
} GistSortedBuildLevelState;

/* 私有函数的原型 */

static void fc_gistSortedBuildCallback(Relation fc_index, ItemPointer fc_tid,
									Datum *fc_values, bool *fc_isnull,
									bool fc_tupleIsAlive, void *fc_state);
static void fc_gist_indexsortbuild(GISTBuildState *fc_state);
static void fc_gist_indexsortbuild_levelstate_add(GISTBuildState *fc_state,
											   GistSortedBuildLevelState *fc_levelstate,
											   IndexTuple fc_itup);
static void fc_gist_indexsortbuild_levelstate_flush(GISTBuildState *fc_state,
												 GistSortedBuildLevelState *fc_levelstate);
static void fc_gist_indexsortbuild_flush_ready_pages(GISTBuildState *fc_state);

static void fc_gistInitBuffering(GISTBuildState *fc_buildstate);
static int	fc_calculatePagesPerBuffer(GISTBuildState *fc_buildstate, int fc_levelStep);
static void fc_gistBuildCallback(Relation fc_index,
							  ItemPointer fc_tid,
							  Datum *fc_values,
							  bool *fc_isnull,
							  bool fc_tupleIsAlive,
							  void *fc_state);
static void fc_gistBufferingBuildInsert(GISTBuildState *fc_buildstate,
									 IndexTuple fc_itup);
static bool fc_gistProcessItup(GISTBuildState *fc_buildstate, IndexTuple fc_itup,
							BlockNumber fc_startblkno, int fc_startlevel);
static BlockNumber fc_gistbufferinginserttuples(GISTBuildState *fc_buildstate,
											 Buffer fc_buffer, int fc_level,
											 IndexTuple *fc_itup, int fc_ntup, OffsetNumber fc_oldoffnum,
											 BlockNumber fc_parentblk, OffsetNumber fc_downlinkoffnum);
static Buffer fc_gistBufferingFindCorrectParent(GISTBuildState *fc_buildstate,
											 BlockNumber fc_childblkno, int fc_level,
											 BlockNumber *fc_parentblk,
											 OffsetNumber *fc_downlinkoffnum);
static void fc_gistProcessEmptyingQueue(GISTBuildState *fc_buildstate);
static void fc_gistEmptyAllBuffers(GISTBuildState *fc_buildstate);
static int	fc_gistGetMaxLevel(Relation fc_index);

static void fc_gistInitParentMap(GISTBuildState *fc_buildstate);
static void fc_gistMemorizeParent(GISTBuildState *fc_buildstate, BlockNumber fc_child,
							   BlockNumber fc_parent);
static void fc_gistMemorizeAllDownlinks(GISTBuildState *fc_buildstate, Buffer fc_parent);
static BlockNumber fc_gistGetParent(GISTBuildState *fc_buildstate, BlockNumber fc_child);


/*
 * GiST索引构建的主要入口点。
 */
IndexBuildResult * gistbuild(Relation fc_heap, Relation fc_index, IndexInfo *fc_indexInfo)
{
	IndexBuildResult *fc_result;
	double		fc_reltuples;
	GISTBuildState fc_buildstate;
	MemoryContext fc_oldcxt = CurrentMemoryContext;
	int			fc_fillfactor;
	Oid			fc_SortSupportFnOids[INDEX_MAX_KEYS];
	GiSTOptions *fc_options = (GiSTOptions *) fc_index->rd_options;

	/*
	 * 我们希望每个索引关系恰好调用一次。如果不是，
	 * 那将是大麻烦。
	 */
	if (RelationGetNumberOfBlocks(fc_index) != 0)
		elog(ERROR, "index \"%s\" already contains data",
			 RelationGetRelationName(fc_index));

	fc_buildstate.indexrel = fc_index;
	fc_buildstate.heaprel = fc_heap;
	fc_buildstate.sortstate = NULL;
	fc_buildstate.giststate = initGISTstate(fc_index);

	/*
	 * 创建一个临时内存上下文，该上下文在处理的每个元组
	 * 之后重置一次。（注意：我们没有麻烦将其作为
	 * giststate的scanCxt的子项，因此必须在最后单独删除。）
	 */
	fc_buildstate.giststate->tempCxt = createTempGistContext();

	/*
	 * 选择构建策略。首先检查用户是否指定使用
	 * 缓冲模式。（在实际应用中，这种用例可能有些
	 * 值得怀疑，但对于测试目的非常重要。）
	 */
	if (fc_options)
	{
		if (fc_options->buffering_mode == GIST_OPTION_BUFFERING_ON)
			fc_buildstate.buildMode = GIST_BUFFERING_STATS;
		else if (fc_options->buffering_mode == GIST_OPTION_BUFFERING_OFF)
			fc_buildstate.buildMode = GIST_BUFFERING_DISABLED;
		else					/* 必须是“auto” */
			fc_buildstate.buildMode = GIST_BUFFERING_AUTO;
	}
	else
	{
		fc_buildstate.buildMode = GIST_BUFFERING_AUTO;
	}

	/*
	 * 除非强制使用缓冲模式，否则看看是否可以使用排序。
	 */
	if (fc_buildstate.buildMode != GIST_BUFFERING_STATS)
	{
		bool		fc_hasallsortsupports = true;
		int			fc_keyscount = IndexRelationGetNumberOfKeyAttributes(fc_index);

		for (int fc_i = 0; fc_i < fc_keyscount; fc_i++)
		{
			fc_SortSupportFnOids[fc_i] = index_getprocid(fc_index, fc_i + 1,
												   GIST_SORTSUPPORT_PROC);
			if (!OidIsValid(fc_SortSupportFnOids[fc_i]))
			{
				fc_hasallsortsupports = false;
				break;
			}
		}
		if (fc_hasallsortsupports)
			fc_buildstate.buildMode = GIST_SORTED_BUILD;
	}

	/*
	 * 计算在页面上留出的目标空闲空间量。
	 */
	fc_fillfactor = fc_options ? fc_options->fillfactor : GIST_DEFAULT_FILLFACTOR;
	fc_buildstate.freespace = BLCKSZ * (100 - fc_fillfactor) / 100;

	/*
	 * 使用选择的策略构建索引。
	 */
	fc_buildstate.indtuples = 0;
	fc_buildstate.indtuplesSize = 0;

	if (fc_buildstate.buildMode == GIST_SORTED_BUILD)
	{
		/*
		 * 排序所有数据，自下而上构建索引。
		 */
		fc_buildstate.sortstate = tuplesort_begin_index_gist(fc_heap,
														  fc_index,
														  maintenance_work_mem,
														  NULL,
														  TUPLESORT_NONE);

		/* 扫描表，将所有元组添加到元组排序中 */
		fc_reltuples = table_index_build_scan(fc_heap, fc_index, fc_indexInfo, true, true,
										   fc_gistSortedBuildCallback,
										   (void *) &fc_buildstate, NULL);

		/*
		 * 执行排序并构建索引页面。
		 */
		tuplesort_performsort(fc_buildstate.sortstate);

		fc_gist_indexsortbuild(&fc_buildstate);

		tuplesort_end(fc_buildstate.sortstate);
	}
	else
	{
		/*
		 * 初始化一个空索引，并插入所有元组，可能在中间层使用缓冲区。
		 */
		Buffer		fc_buffer;
		Page		fc_page;

		/* 初始化根页面 */
		fc_buffer = gistNewBuffer(fc_index);
		Assert(BufferGetBlockNumber(fc_buffer) == GIST_ROOT_BLKNO);
		fc_page = BufferGetPage(fc_buffer);

		START_CRIT_SECTION();

		GISTInitBuffer(fc_buffer, F_LEAF);

		MarkBufferDirty(fc_buffer);
		PageSetLSN(fc_page, GistBuildLSN);

		UnlockReleaseBuffer(fc_buffer);

		END_CRIT_SECTION();

		/* 扫描表，插入所有元组到索引中。 */
		fc_reltuples = table_index_build_scan(fc_heap, fc_index, fc_indexInfo, true, true,
										   fc_gistBuildCallback,
										   (void *) &fc_buildstate, NULL);

		/*
		 * 如果使用了缓冲，则将所有仍在缓冲区中的元组刷新出去。
		 */
		if (fc_buildstate.buildMode == GIST_BUFFERING_ACTIVE)
		{
			elog(DEBUG1, "all tuples processed, emptying buffers");
			fc_gistEmptyAllBuffers(&fc_buildstate);
			gistFreeBuildBuffers(fc_buildstate.gfbb);
		}

		/*
		 * 在构建索引时我们没有写入WAL记录，因此如果需要WAL日志，
		 * 现在将所有页面写入WAL。
		 */
		if (RelationNeedsWAL(fc_index))
		{
			log_newpage_range(fc_index, MAIN_FORKNUM,
							  0, RelationGetNumberOfBlocks(fc_index),
							  true);
		}
	}

	/* 好的，所有堆元组都已被索引 */
	MemoryContextSwitchTo(fc_oldcxt);
	MemoryContextDelete(fc_buildstate.giststate->tempCxt);

	freeGISTstate(fc_buildstate.giststate);

	/*
	 * 返回统计信息
	 */
	fc_result = (IndexBuildResult *) palloc(sizeof(IndexBuildResult));

	fc_result->heap_tuples = fc_reltuples;
	fc_result->index_tuples = (double) fc_buildstate.indtuples;

	return fc_result;
}

/*-------------------------------------------------------------------------
 * 用于排序构建的例程
 *-------------------------------------------------------------------------
 */

/*
 * 每个元组的回调，用于table_index_build_scan。
 */
static void fc_gistSortedBuildCallback(Relation fc_index,
						ItemPointer fc_tid,
						Datum *fc_values,
						bool *fc_isnull,
						bool fc_tupleIsAlive,
						void *fc_state)
{
	GISTBuildState *fc_buildstate = (GISTBuildState *) fc_state;
	MemoryContext fc_oldCtx;
	Datum		fc_compressed_values[INDEX_MAX_KEYS];

	fc_oldCtx = MemoryContextSwitchTo(fc_buildstate->giststate->tempCxt);

	/* 形成一个索引元组并指向堆元组 */
	gistCompressValues(fc_buildstate->giststate, fc_index,
					   fc_values, fc_isnull,
					   true, fc_compressed_values);

	tuplesort_putindextuplevalues(fc_buildstate->sortstate,
								  fc_buildstate->indexrel,
								  fc_tid,
								  fc_compressed_values, fc_isnull);

	MemoryContextSwitchTo(fc_oldCtx);
	MemoryContextReset(fc_buildstate->giststate->tempCxt);

	/* 更新元组计数。 */
	fc_buildstate->indtuples += 1;
}

/*
 * 从已排序的元组自下而上构建GiST索引。
 */
static void fc_gist_indexsortbuild(GISTBuildState *fc_state)
{
	IndexTuple	fc_itup;
	GistSortedBuildLevelState *fc_levelstate;
	Page		fc_page;

	fc_state->pages_allocated = 0;
	fc_state->pages_written = 0;
	fc_state->ready_num_pages = 0;

	/*
	 * 写入一个空页面作为根页面的占位符。它将在最后
	 * 被真实的根页面替换。
	 */
	fc_page = palloc0(BLCKSZ);
	smgrextend(RelationGetSmgr(fc_state->indexrel), MAIN_FORKNUM, GIST_ROOT_BLKNO,
			   fc_page, true);
	fc_state->pages_allocated++;
	fc_state->pages_written++;

	/* 为第一个叶页面批次分配一个临时缓冲区。 */
	fc_levelstate = palloc0(sizeof(GistSortedBuildLevelState));
	fc_levelstate->pages[0] = fc_page;
	fc_levelstate->parent = NULL;
	gistinitpage(fc_page, F_LEAF);

	/*
	 * 按照排序顺序用元组填充索引页面。
	 */
	while ((fc_itup = tuplesort_getindextuple(fc_state->sortstate, true)) != NULL)
	{
		fc_gist_indexsortbuild_levelstate_add(fc_state, fc_levelstate, fc_itup);
		MemoryContextReset(fc_state->giststate->tempCxt);
	}

	/*
	 * 写出部分填充的非根页面。
	 *
	 * 请记住，刷新可能构建新根。如果页面数量 > 1
	 * 则需要新的根。
	 */
	while (fc_levelstate->parent != NULL || fc_levelstate->current_page != 0)
	{
		GistSortedBuildLevelState *fc_parent;

		fc_gist_indexsortbuild_levelstate_flush(fc_state, fc_levelstate);
		fc_parent = fc_levelstate->parent;
		for (int fc_i = 0; fc_i < GIST_SORTED_BUILD_PAGE_NUM; fc_i++)
			if (fc_levelstate->pages[fc_i])
				pfree(fc_levelstate->pages[fc_i]);
		pfree(fc_levelstate);
		fc_levelstate = fc_parent;
	}

	fc_gist_indexsortbuild_flush_ready_pages(fc_state);

	/* 写出根页面 */
	PageSetLSN(fc_levelstate->pages[0], GistBuildLSN);
	PageSetChecksumInplace(fc_levelstate->pages[0], GIST_ROOT_BLKNO);
	smgrwrite(RelationGetSmgr(fc_state->indexrel), MAIN_FORKNUM, GIST_ROOT_BLKNO,
			  fc_levelstate->pages[0], true);
	if (RelationNeedsWAL(fc_state->indexrel))
		log_newpage(&fc_state->indexrel->rd_node, MAIN_FORKNUM, GIST_ROOT_BLKNO,
					fc_levelstate->pages[0], true);

	pfree(fc_levelstate->pages[0]);
	pfree(fc_levelstate);

	/*
	 * 当我们WAL-记录索引页面时，我们仍然必须fsync索引文件。
	 * 由于我们是在共享缓冲区之外构建的，在构建过程中发生的CHECKPOINT
	 * 没有办法将先前写入的数据刷新到磁盘（实际上它甚至不知道该索引存在）。
	 * 后来的崩溃将从检查点重新播放WAL，因此不会重放我们
	 * 之前的WAL条目。如果我们不在这里fsync这些页面，
	 * 则当崩溃发生时它们可能仍然不在磁盘上。
	 */
	if (RelationNeedsWAL(fc_state->indexrel))
		smgrimmedsync(RelationGetSmgr(fc_state->indexrel), MAIN_FORKNUM);
}

/*
 * 将元组添加到页面。如果页面已满，则将其写出并重新初始化
 * 一个新页面。
 */
static void fc_gist_indexsortbuild_levelstate_add(GISTBuildState *fc_state,
								   GistSortedBuildLevelState *fc_levelstate,
								   IndexTuple fc_itup)
{
	Size		fc_sizeNeeded;

	/* 检查元组是否可以添加到当前页面 */
	fc_sizeNeeded = IndexTupleSize(fc_itup) + sizeof(ItemIdData); /* 填充值被忽略 */
	if (PageGetFreeSpace(fc_levelstate->pages[fc_levelstate->current_page]) < fc_sizeNeeded)
	{
		Page		fc_newPage;
		Page		fc_old_page = fc_levelstate->pages[fc_levelstate->current_page];
		uint16		fc_old_page_flags = GistPageGetOpaque(fc_old_page)->flags;

		if (fc_levelstate->current_page + 1 == GIST_SORTED_BUILD_PAGE_NUM)
		{
			fc_gist_indexsortbuild_levelstate_flush(fc_state, fc_levelstate);
		}
		else
			fc_levelstate->current_page++;

		if (fc_levelstate->pages[fc_levelstate->current_page] == NULL)
			fc_levelstate->pages[fc_levelstate->current_page] = palloc(BLCKSZ);

		fc_newPage = fc_levelstate->pages[fc_levelstate->current_page];
		gistinitpage(fc_newPage, fc_old_page_flags);
	}

	gistfillbuffer(fc_levelstate->pages[fc_levelstate->current_page], &fc_itup, 1, InvalidOffsetNumber);
}

static void fc_gist_indexsortbuild_levelstate_flush(GISTBuildState *fc_state,
									 GistSortedBuildLevelState *fc_levelstate)
{
	GistSortedBuildLevelState *fc_parent;
	BlockNumber fc_blkno;
	MemoryContext fc_oldCtx;
	IndexTuple	fc_union_tuple;
	SplitedPageLayout *fc_dist;
	IndexTuple *fc_itvec;
	int			fc_vect_len;
	bool		fc_isleaf = GistPageIsLeaf(fc_levelstate->pages[0]);

	CHECK_FOR_INTERRUPTS();

	fc_oldCtx = MemoryContextSwitchTo(fc_state->giststate->tempCxt);

	/* 从第一页获取索引元组 */
	fc_itvec = gistextractpage(fc_levelstate->pages[0], &fc_vect_len);
	if (fc_levelstate->current_page > 0)
	{
		/* 从每一页附加元组 */
		for (int fc_i = 1; fc_i < fc_levelstate->current_page + 1; fc_i++)
		{
			int			fc_len_local;
			IndexTuple *fc_itvec_local = gistextractpage(fc_levelstate->pages[fc_i], &fc_len_local);

			fc_itvec = gistjoinvector(fc_itvec, &fc_vect_len, fc_itvec_local, fc_len_local);
			pfree(fc_itvec_local);
		}

		/* 对所有收集到的元组应用picksplit */
		fc_dist = gistSplit(fc_state->indexrel, fc_levelstate->pages[0], fc_itvec, fc_vect_len, fc_state->giststate);
	}
	else
	{
		/* 从单一页面创建分裂布局 */
		fc_dist = (SplitedPageLayout *) palloc0(sizeof(SplitedPageLayout));
		fc_union_tuple = gistunion(fc_state->indexrel, fc_itvec, fc_vect_len,
								fc_state->giststate);
		fc_dist->itup = fc_union_tuple;
		fc_dist->list = gistfillitupvec(fc_itvec, fc_vect_len, &(fc_dist->lenlist));
		fc_dist->block.num = fc_vect_len;
	}

	MemoryContextSwitchTo(fc_oldCtx);

	/* 重置页面计数器 */
	fc_levelstate->current_page = 0;

	/* 为分裂结果中的所有分区创建页面 */
	for (; fc_dist != NULL; fc_dist = fc_dist->next)
	{
		char	   *fc_data;
		Page		fc_target;

		/* 每页检查一次 */
		CHECK_FOR_INTERRUPTS();

		/* 创建页面并复制数据 */
		fc_data = (char *) (fc_dist->list);
		fc_target = palloc0(BLCKSZ);
		gistinitpage(fc_target, fc_isleaf ? F_LEAF : 0);
		for (int fc_i = 0; fc_i < fc_dist->block.num; fc_i++)
		{
			IndexTuple	fc_thistup = (IndexTuple) fc_data;

			if (PageAddItem(fc_target, (Item) fc_data, IndexTupleSize(fc_thistup), fc_i + FirstOffsetNumber, false, false) == InvalidOffsetNumber)
				elog(ERROR, "failed to add item to index page in \"%s\"", RelationGetRelationName(fc_state->indexrel));

			fc_data += IndexTupleSize(fc_thistup);
		}
		fc_union_tuple = fc_dist->itup;

		if (fc_state->ready_num_pages == XLR_MAX_BLOCK_ID)
			fc_gist_indexsortbuild_flush_ready_pages(fc_state);

		/*
		 * 页面现在已完成。为其分配一个块编号，并将其
		 * 添加到已完成页面的列表中。（我们不立即写出它，
		 * 因为我们想批量WAL-记录这些页面。）
		 */
		fc_blkno = fc_state->pages_allocated++;
		fc_state->ready_blknos[fc_state->ready_num_pages] = fc_blkno;
		fc_state->ready_pages[fc_state->ready_num_pages] = fc_target;
		fc_state->ready_num_pages++;
		ItemPointerSetBlockNumber(&(fc_union_tuple->t_tid), fc_blkno);

		/*
		 * 设置右链接指向上一页。这只是
		 * 调试目的：GiST 仅在页面与扫描同时拆分时遵循右链接，而
		 * 这种情况不能在索引构建期间发生。
		 *
		 * 让新页面的右链接指向上一页这一点有点反直觉，而不是反过来。但是
		 * GiST 页面并不像 B-tree 页面那样有序，因此只要右链接在
		 * 同一层的所有页面之间形成链条，顺序并不重要。
		 */
		if (fc_levelstate->last_blkno)
			GistPageGetOpaque(fc_target)->rightlink = fc_levelstate->last_blkno;
		fc_levelstate->last_blkno = fc_blkno;

		/*
		 * 将下链接插入到父页面。如果这是根，
		 * 则创建一个新页面作为父页面，成为新的根。
		 */
		fc_parent = fc_levelstate->parent;
		if (fc_parent == NULL)
		{
			fc_parent = palloc0(sizeof(GistSortedBuildLevelState));
			fc_parent->pages[0] = (Page) palloc(BLCKSZ);
			fc_parent->parent = NULL;
			gistinitpage(fc_parent->pages[0], 0);

			fc_levelstate->parent = fc_parent;
		}
		fc_gist_indexsortbuild_levelstate_add(fc_state, fc_parent, fc_union_tuple);
	}
}

static void fc_gist_indexsortbuild_flush_ready_pages(GISTBuildState *fc_state)
{
	if (fc_state->ready_num_pages == 0)
		return;

	for (int fc_i = 0; fc_i < fc_state->ready_num_pages; fc_i++)
	{
		Page		fc_page = fc_state->ready_pages[fc_i];
		BlockNumber fc_blkno = fc_state->ready_blknos[fc_i];

		/* 目前，块必须按顺序缓冲。 */
		if (fc_blkno != fc_state->pages_written)
			elog(ERROR, "unexpected block number to flush GiST sorting build");

		PageSetLSN(fc_page, GistBuildLSN);
		PageSetChecksumInplace(fc_page, fc_blkno);
		smgrextend(RelationGetSmgr(fc_state->indexrel), MAIN_FORKNUM, fc_blkno, fc_page,
				   true);

		fc_state->pages_written++;
	}

	if (RelationNeedsWAL(fc_state->indexrel))
		log_newpages(&fc_state->indexrel->rd_node, MAIN_FORKNUM, fc_state->ready_num_pages,
					 fc_state->ready_blknos, fc_state->ready_pages, true);

	for (int fc_i = 0; fc_i < fc_state->ready_num_pages; fc_i++)
		pfree(fc_state->ready_pages[fc_i]);

	fc_state->ready_num_pages = 0;
}


/*-------------------------------------------------------------------------
 * 非排序构建的例程
 *-------------------------------------------------------------------------
 */

/*
 * 尝试切换到缓冲模式。
 *
 * 如果没有足够的内存用于缓冲构建，将 bufferingMode 设置为 
 * GIST_BUFFERING_DISABLED，以便我们不再费心尝试切换。
 * 否则初始化构建缓冲区，并将 bufferingMode 设置为 
 * GIST_BUFFERING_ACTIVE。
 */
static void fc_gistInitBuffering(GISTBuildState *fc_buildstate)
{
	Relation	fc_index = fc_buildstate->indexrel;
	int			fc_pagesPerBuffer;
	Size		fc_pageFreeSpace;
	Size		fc_itupAvgSize,
				fc_itupMinSize;
	double		fc_avgIndexTuplesPerPage,
				fc_maxIndexTuplesPerPage;
	int			fc_i;
	int			fc_levelStep;

	/* 计算索引页面中可用于索引元组的空间 */
	fc_pageFreeSpace = BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)
		- sizeof(ItemIdData)
		- fc_buildstate->freespace;

	/*
	 * 使用收集的统计信息计算已插入索引元组的平均大小。
	 */
	fc_itupAvgSize = (double) fc_buildstate->indtuplesSize /
		(double) fc_buildstate->indtuples;

	/*
	 * 通过索引元数据计算索引元组的最小可能大小。
	 * varlena 的最小可能大小是 VARHDRSZ。
	 *
	 * XXX：这实际上并不正确，因为短 varlen 可能只有 2 字节。
	 * 我们还应该考虑填充。
	 */
	fc_itupMinSize = (Size) MAXALIGN(sizeof(IndexTupleData));
	for (fc_i = 0; fc_i < fc_index->rd_att->natts; fc_i++)
	{
		if (TupleDescAttr(fc_index->rd_att, fc_i)->attlen < 0)
			fc_itupMinSize += VARHDRSZ;
		else
			fc_itupMinSize += TupleDescAttr(fc_index->rd_att, fc_i)->attlen;
	}

	/* 计算适合页面的索引元组的平均和最大数量 */
	fc_avgIndexTuplesPerPage = fc_pageFreeSpace / fc_itupAvgSize;
	fc_maxIndexTuplesPerPage = fc_pageFreeSpace / fc_itupMinSize;

	/*
	 * 我们需要为缓冲算法计算两个参数：
	 * levelStep 和 pagesPerBuffer。
	 *
	 * levelStep 决定了在清空缓冲区时我们操作的子树的大小。更高的值更好，因为构建索引时需要更少的缓冲区清空步骤。然而，如果设置得太高，子树将不再适合缓存，您会迅速失去缓冲区的好处。
	 *
	 * 在 Arge 等人的论文中，levelStep 被选择为 logB(M/4B)，其中 B 是页面上元组的数量（即分支因子），M 是可用的内部内存量。奇怪的是，他们没有解释 *为什么* 这个设置是最优的。我们通过取最高的 levelStep 来计算，以便子树仍然适合缓存。对于小 B，我们计算 levelStep 的方法与 Arge 等人的公式非常接近。对于大 B，我们的公式给出的值高出 2 倍。
	 *
	 * 深度 n 子树的平均大小（以页面为单位）可以计算为几何级数：
	 *
	 * B^0 + B^1 + B^2 + ... + B^n = (1 - B^(n + 1)) / (1 - B)
	 *
	 * 其中 B 是页面上索引元组的平均数量。子树保存在共享缓冲区缓存和操作系统缓存中，因此我们选择 levelStep，使得子树大小明显小于 effective_cache_size，并且有一个安全系数为 4。
	 *
	 * 关于页面上索引元组的平均数量的估计是基于切换到缓冲构建之前观察到的平均元组大小，因此实际的子树大小可能会大一些。此外，贪婪地占用整个缓存来构建索引是不合适的。4 的安全系数应该考虑到这些影响。
	 *
	 * 设置 levelStep 的另一个限制因素是，在处理子树时，我们需要为下一个较低缓冲级别的每个缓冲区保留一个页面。所需的最大缓冲区数量是 maxIndexTuplesPerPage^levelStep。这是非常保守的，但希望 maintenance_work_mem 设置得足够高，以便您受到 effective_cache_size 的限制，而不是 maintenance_work_mem。
	 *
	 * XXX: 缓冲哈希表每个缓冲区也消耗相当数量的内存，但目前没有考虑到。这取决于所用的缓冲区总数，即索引大小和 levelStep。请注意，更高的 levelStep *减少* 哈希表所需的内存量。
	 */
	fc_levelStep = 1;
	for (;;)
	{
		double		fc_subtreesize;
		double		fc_maxlowestlevelpages;

		/* 该 levelStep 下平均子树的大小（以页面为单位）。 */
		fc_subtreesize =
			(1 - pow(fc_avgIndexTuplesPerPage, (double) (fc_levelStep + 1))) /
			(1 - fc_avgIndexTuplesPerPage);

		/* 子树最低级别的最大页面数量 */
		fc_maxlowestlevelpages = pow(fc_maxIndexTuplesPerPage, (double) fc_levelStep);

		/* 子树必须适合缓存（安全系数为 4） */
		if (fc_subtreesize > effective_cache_size / 4)
			break;

		/* 子树最低级别的每个节点在内存中占用一个页面 */
		if (fc_maxlowestlevelpages > ((double) maintenance_work_mem * 1024) / BLCKSZ)
			break;

		/* 好的，我们可以处理这个 levelStep。看看我们是否可以再高一些。 */
		fc_levelStep++;
	}

	/*
	 * 我们在之前的循环中刚刚达到了不可接受的 levelStep 值。
	 * 所以，降低 levelStep 以获得最后一个可接受值。
	 */
	fc_levelStep--;

	/*
	 * 如果没有足够的缓存或 maintenance_work_mem，则退回到普通插入。
	 */
	if (fc_levelStep <= 0)
	{
		elog(DEBUG1, "failed to switch to buffered GiST build");
		fc_buildstate->buildMode = GIST_BUFFERING_DISABLED;
		return;
	}

	/*
	 * 设置的第二个参数是 pagesPerBuffer，它决定了每个缓冲区的大小。
	 * 我们在构建期间也会调整 pagesPerBuffer，这就是为什么这个计算在一个单独的函数中的原因。
	 */
	fc_pagesPerBuffer = fc_calculatePagesPerBuffer(fc_buildstate, fc_levelStep);

	/* 用这些参数初始化 GISTBuildBuffers */
	fc_buildstate->gfbb = gistInitBuildBuffers(fc_pagesPerBuffer, fc_levelStep,
											fc_gistGetMaxLevel(fc_index));

	fc_gistInitParentMap(fc_buildstate);

	fc_buildstate->buildMode = GIST_BUFFERING_ACTIVE;

	elog(DEBUG1, "switched to buffered GiST build; level step = %d, pagesPerBuffer = %d",
		 fc_levelStep, fc_pagesPerBuffer);
}

/*
 * 计算缓冲算法的 pagesPerBuffer 参数。
 *
 * 缓冲区大小的选择是基于假设元组是随机分布的，清空一半缓冲区平均在下一个更低级别的每个缓冲区填充一个页面。
 */
static int fc_calculatePagesPerBuffer(GISTBuildState *fc_buildstate, int fc_levelStep)
{
	double		fc_pagesPerBuffer;
	double		fc_avgIndexTuplesPerPage;
	double		fc_itupAvgSize;
	Size		fc_pageFreeSpace;

	/* 计算索引页面中可用于索引元组的空间 */
	fc_pageFreeSpace = BLCKSZ - SizeOfPageHeaderData - sizeof(GISTPageOpaqueData)
		- sizeof(ItemIdData)
		- fc_buildstate->freespace;

	/*
	 * 使用收集的统计信息计算已插入索引元组的平均大小。
	 */
	fc_itupAvgSize = (double) fc_buildstate->indtuplesSize /
		(double) fc_buildstate->indtuples;

	fc_avgIndexTuplesPerPage = fc_pageFreeSpace / fc_itupAvgSize;

	/*
	 * 重新计算所需的缓冲区大小。
	 */
	fc_pagesPerBuffer = 2 * pow(fc_avgIndexTuplesPerPage, fc_levelStep);

	return (int) rint(fc_pagesPerBuffer);
}

/*
 * 每个元组的回调，用于table_index_build_scan。
 */
static void fc_gistBuildCallback(Relation fc_index,
				  ItemPointer fc_tid,
				  Datum *fc_values,
				  bool *fc_isnull,
				  bool fc_tupleIsAlive,
				  void *fc_state)
{
	GISTBuildState *fc_buildstate = (GISTBuildState *) fc_state;
	IndexTuple	fc_itup;
	MemoryContext fc_oldCtx;

	fc_oldCtx = MemoryContextSwitchTo(fc_buildstate->giststate->tempCxt);

	/* 形成一个索引元组并指向堆元组 */
	fc_itup = gistFormTuple(fc_buildstate->giststate, fc_index,
						 fc_values, fc_isnull,
						 true);
	fc_itup->t_tid = *fc_tid;

	/* 更新元组计数和总大小。 */
	fc_buildstate->indtuples += 1;
	fc_buildstate->indtuplesSize += IndexTupleSize(fc_itup);

	/*
	 * XXX 在缓冲构建中，tempCxt 也会在 gistProcessEmptyingQueue() 内部重置。
	 * 这并不好，因为这增加了混淆和可能使用悬空指针的风险（例如，当控制返回到这里时，itup 可能已经被释放）。
	 * 一般来说，一个内存上下文应该只由一个函数“拥有”。不过，目前这并没有造成问题，
	 * 因此似乎不值得进行避免这种情况所需的重构。
	 */
	if (fc_buildstate->buildMode == GIST_BUFFERING_ACTIVE)
	{
		/* 我们有缓冲区，因此使用它们。 */
		fc_gistBufferingBuildInsert(fc_buildstate, fc_itup);
	}
	else
	{
		/*
		 * 还没有缓冲区。由于我们已经锁定了索引关系，因此直接调用 gistdoinsert。
		 */
		gistdoinsert(fc_index, fc_itup, fc_buildstate->freespace,
					 fc_buildstate->giststate, fc_buildstate->heaprel, true);
	}

	MemoryContextSwitchTo(fc_oldCtx);
	MemoryContextReset(fc_buildstate->giststate->tempCxt);

	if (fc_buildstate->buildMode == GIST_BUFFERING_ACTIVE &&
		fc_buildstate->indtuples % BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET == 0)
	{
		/* 现在调整目标缓冲区大小 */
		fc_buildstate->gfbb->pagesPerBuffer =
			fc_calculatePagesPerBuffer(fc_buildstate, fc_buildstate->gfbb->levelStep);
	}

	/*
	 * 在“自动”模式下，检查索引是否增长到过大而无法适应缓存，
	 * 如果是，则切换到缓冲模式。
	 *
	 * 为了避免过多调用 smgrnblocks()，每 BUFFERING_MODE_SWITCH_CHECK_STEP 个索引元组只检查一次。
	 *
	 * 在“统计”状态下，一旦我们看到了足够多的元组以大致了解平均元组大小，就立即切换。
	 */
	if ((fc_buildstate->buildMode == GIST_BUFFERING_AUTO &&
		 fc_buildstate->indtuples % BUFFERING_MODE_SWITCH_CHECK_STEP == 0 &&
		 effective_cache_size < smgrnblocks(RelationGetSmgr(fc_index),
											MAIN_FORKNUM)) ||
		(fc_buildstate->buildMode == GIST_BUFFERING_STATS &&
		 fc_buildstate->indtuples >= BUFFERING_MODE_TUPLE_SIZE_STATS_TARGET))
	{
		/*
		 * 索引不再适合有效缓存。尝试切换到缓冲构建模式。
		 */
		fc_gistInitBuffering(fc_buildstate);
	}
}

/*
 * 用于缓冲索引构建的插入函数。
 */
static void fc_gistBufferingBuildInsert(GISTBuildState *fc_buildstate, IndexTuple fc_itup)
{
	/* 将元组插入到缓冲区。 */
	fc_gistProcessItup(fc_buildstate, fc_itup, 0, fc_buildstate->gfbb->rootlevel);

	/* 如果我们填满了（半个）缓冲区，则处理缓冲区清空。 */
	fc_gistProcessEmptyingQueue(fc_buildstate);
}

/*
 * 处理一个索引元组。将元组向下运行到树中，直到我们到达叶节点页面或节点缓冲区，并在那插入元组。
 * 如果我们必须停止缓冲区清空过程（因为一个子缓冲区无法再接收索引元组），则返回 true。
 */
static bool fc_gistProcessItup(GISTBuildState *fc_buildstate, IndexTuple fc_itup,
				BlockNumber fc_startblkno, int fc_startlevel)
{
	GISTSTATE  *fc_giststate = fc_buildstate->giststate;
	GISTBuildBuffers *fc_gfbb = fc_buildstate->gfbb;
	Relation	fc_indexrel = fc_buildstate->indexrel;
	BlockNumber fc_childblkno;
	Buffer		fc_buffer;
	bool		fc_result = false;
	BlockNumber fc_blkno;
	int			fc_level;
	OffsetNumber fc_downlinkoffnum = InvalidOffsetNumber;
	BlockNumber fc_parentblkno = InvalidBlockNumber;

	CHECK_FOR_INTERRUPTS();

	/*
	 * 循环直到我们到达一个叶页面（level == 0）或一个有缓冲区的级别
	 * （不包括我们开始时的级别，因为我们不然将无法取得进展）。
	 */
	fc_blkno = fc_startblkno;
	fc_level = fc_startlevel;
	for (;;)
	{
		ItemId		fc_iid;
		IndexTuple	fc_idxtuple,
					fc_newtup;
		Page		fc_page;
		OffsetNumber fc_childoffnum;

		/* 我们是否到达了一个有缓冲区的级别？ */
		if (LEVEL_HAS_BUFFERS(fc_level, fc_gfbb) && fc_level != fc_startlevel)
			break;

		/* 我们是否到达了叶页面？ */
		if (fc_level == 0)
			break;

		/*
		 * 不。这就降到下一级去。选择一个子节点降下去。
		 */

		fc_buffer = ReadBuffer(fc_indexrel, fc_blkno);
		LockBuffer(fc_buffer, GIST_EXCLUSIVE);

		fc_page = (Page) BufferGetPage(fc_buffer);
		fc_childoffnum = gistchoose(fc_indexrel, fc_page, fc_itup, fc_giststate);
		fc_iid = PageGetItemId(fc_page, fc_childoffnum);
		fc_idxtuple = (IndexTuple) PageGetItem(fc_page, fc_iid);
		fc_childblkno = ItemPointerGetBlockNumber(&(fc_idxtuple->t_tid));

		if (fc_level > 1)
			fc_gistMemorizeParent(fc_buildstate, fc_childblkno, fc_blkno);

		/*
		 * 检查表示目标子节点的键是否与我们要插入的键一致。
		 * 如果不一致，则更新它。
		 */
		fc_newtup = gistgetadjusted(fc_indexrel, fc_idxtuple, fc_itup, fc_giststate);
		if (fc_newtup)
		{
			fc_blkno = fc_gistbufferinginserttuples(fc_buildstate,
											  fc_buffer,
											  fc_level,
											  &fc_newtup,
											  1,
											  fc_childoffnum,
											  InvalidBlockNumber,
											  InvalidOffsetNumber);
			/* gistbufferinginserttuples() 释放了缓冲区 */
		}
		else
			UnlockReleaseBuffer(fc_buffer);

		/* 降到子节点 */
		fc_parentblkno = fc_blkno;
		fc_blkno = fc_childblkno;
		fc_downlinkoffnum = fc_childoffnum;
		Assert(fc_level > 0);
		fc_level--;
	}

	if (LEVEL_HAS_BUFFERS(fc_level, fc_gfbb))
	{
		/*
		 * 我们已经到达了具有缓冲区的层级。将索引元组放入缓冲区，
		 * 如果缓冲区溢出，则将缓冲区添加到清空队列中。
		 */
		GISTNodeBuffer *fc_childNodeBuffer;

		/* 查找缓冲区或创建一个新缓冲区 */
		fc_childNodeBuffer = gistGetNodeBuffer(fc_gfbb, fc_giststate, fc_blkno, fc_level);

		/* 将索引元组添加到其中 */
		gistPushItupToNodeBuffer(fc_gfbb, fc_childNodeBuffer, fc_itup);

		if (BUFFER_OVERFLOWED(fc_childNodeBuffer, fc_gfbb))
			fc_result = true;
	}
	else
	{
		/*
		 * 我们已到达一个叶页。在这里放置元组。
		 */
		Assert(fc_level == 0);
		fc_buffer = ReadBuffer(fc_indexrel, fc_blkno);
		LockBuffer(fc_buffer, GIST_EXCLUSIVE);
		fc_gistbufferinginserttuples(fc_buildstate, fc_buffer, fc_level,
								  &fc_itup, 1, InvalidOffsetNumber,
								  fc_parentblkno, fc_downlinkoffnum);
		/* gistbufferinginserttuples() 释放了缓冲区 */
	}

	return fc_result;
}

/*
 * 向指定页面插入元组。
 *
 * 这与常规插入代码中的 gistinserttuples() 类似。
 *
 * 返回新插入的（第一个）元组所在页面的块号。通常是原始页面，
 * 但如果原始页面被拆分，则可能是一个兄弟页面。
 *
 * 调用者应在入口处持有 'buffer' 的锁。这一功能将解锁
 * 并取消固定。
 */
static BlockNumber fc_gistbufferinginserttuples(GISTBuildState *fc_buildstate, Buffer fc_buffer, int fc_level,
						  IndexTuple *fc_itup, int fc_ntup, OffsetNumber fc_oldoffnum,
						  BlockNumber fc_parentblk, OffsetNumber fc_downlinkoffnum)
{
	GISTBuildBuffers *fc_gfbb = fc_buildstate->gfbb;
	List	   *fc_splitinfo;
	bool		fc_is_split;
	BlockNumber fc_placed_to_blk = InvalidBlockNumber;

	fc_is_split = gistplacetopage(fc_buildstate->indexrel,
							   fc_buildstate->freespace,
							   fc_buildstate->giststate,
							   fc_buffer,
							   fc_itup, fc_ntup, fc_oldoffnum, &fc_placed_to_blk,
							   InvalidBuffer,
							   &fc_splitinfo,
							   false,
							   fc_buildstate->heaprel, true);

	/*
	 * 如果这是一个根拆分，请更新保存在内存中的根路径项。这
	 * 确保所有路径堆栈始终完整，包括所有父节点直到根。
	 * 这简化了重新找到正确父节点的算法。
	 */
	if (fc_is_split && BufferGetBlockNumber(fc_buffer) == GIST_ROOT_BLKNO)
	{
		Page		fc_page = BufferGetPage(fc_buffer);
		OffsetNumber fc_off;
		OffsetNumber fc_maxoff;

		Assert(fc_level == fc_gfbb->rootlevel);
		fc_gfbb->rootlevel++;

		elog(DEBUG2, "splitting GiST root page, now %d levels deep", fc_gfbb->rootlevel);

		/*
		 * 旧根页面上的所有下连接现在位于某个子页面上。访问所有新
		 * 子页面以记住孙子的父节点。
		 */
		if (fc_gfbb->rootlevel > 1)
		{
			fc_maxoff = PageGetMaxOffsetNumber(fc_page);
			for (fc_off = FirstOffsetNumber; fc_off <= fc_maxoff; fc_off++)
			{
				ItemId		fc_iid = PageGetItemId(fc_page, fc_off);
				IndexTuple	fc_idxtuple = (IndexTuple) PageGetItem(fc_page, fc_iid);
				BlockNumber fc_childblkno = ItemPointerGetBlockNumber(&(fc_idxtuple->t_tid));
				Buffer		fc_childbuf = ReadBuffer(fc_buildstate->indexrel, fc_childblkno);

				LockBuffer(fc_childbuf, GIST_SHARE);
				fc_gistMemorizeAllDownlinks(fc_buildstate, fc_childbuf);
				UnlockReleaseBuffer(fc_childbuf);

				/*
				 * 还要记住新子页面的父节点是根块。
				 */
				fc_gistMemorizeParent(fc_buildstate, fc_childblkno, GIST_ROOT_BLKNO);
			}
		}
	}

	if (fc_splitinfo)
	{
		/*
		 * 将下连接插入到父节点。这与常规插入代码中的
		 * gistfinishsplit() 类似，但锁定更简单，并且我们需要
		 * 在内部节点和父映射上维护缓冲区。
		 */
		IndexTuple *fc_downlinks;
		int			fc_ndownlinks,
					fc_i;
		Buffer		fc_parentBuffer;
		ListCell   *fc_lc;

		/* 父节点自我们记住这条路径以来可能发生了变化。 */
		fc_parentBuffer =
			fc_gistBufferingFindCorrectParent(fc_buildstate,
										   BufferGetBlockNumber(fc_buffer),
										   fc_level,
										   &fc_parentblk,
										   &fc_downlinkoffnum);

		/*
		 * 如果此页面有一个关联的缓冲区，则也需要拆分它。
		 * gistRelocateBuildBuffersOnSplit() 还将调整
		 * 'splitinfo' 中的下连接，以确保它们不仅与已在页面上的
		 * 元组一致，还与最终将插入到它们中的缓冲区中的元组一致。
		 */
		gistRelocateBuildBuffersOnSplit(fc_gfbb,
										fc_buildstate->giststate,
										fc_buildstate->indexrel,
										fc_level,
										fc_buffer, fc_splitinfo);

		/* 创建所有下连接元组的数组 */
		fc_ndownlinks = list_length(fc_splitinfo);
		fc_downlinks = (IndexTuple *) palloc(sizeof(IndexTuple) * fc_ndownlinks);
		fc_i = 0;
		foreach(fc_lc, fc_splitinfo)
		{
			GISTPageSplitInfo *fc_splitinfo = lfirst(fc_lc);

			/*
			 * 在我们的父映射中记住每个新子页面的父节点。
			 * 这假设下连接适合在父页面上。如果父页面也被拆分，
			 * 当我们递归向上插入下连接时，递归的 gistbufferinginserttuples()
			 * 调用将再次更新映射。
			 */
			if (fc_level > 0)
				fc_gistMemorizeParent(fc_buildstate,
								   BufferGetBlockNumber(fc_splitinfo->buf),
								   BufferGetBlockNumber(fc_parentBuffer));

			/*
			 * 还更新所有移动到不同页面的下连接的父映射。
			 * （实际上，这也遍历了保留在原始页面上的下连接，但并不
			 * 造成什么伤害）。
			 */
			if (fc_level > 1)
				fc_gistMemorizeAllDownlinks(fc_buildstate, fc_splitinfo->buf);

			/*
			 * 由于没有并发访问，我们可以立即释放较低级别的缓冲区。这包括原始页面。
			 */
			UnlockReleaseBuffer(fc_splitinfo->buf);
			fc_downlinks[fc_i++] = fc_splitinfo->downlink;
		}

		/* 将它们插入父级。 */
		fc_gistbufferinginserttuples(fc_buildstate, fc_parentBuffer, fc_level + 1,
								  fc_downlinks, fc_ndownlinks, fc_downlinkoffnum,
								  InvalidBlockNumber, InvalidOffsetNumber);

		list_free_deep(fc_splitinfo);	/* 我们不再需要这个了 */
	}
	else
		UnlockReleaseBuffer(fc_buffer);

	return fc_placed_to_blk;
}

/*
 * 找到指向子页面的下行链接。
 *
 * 'childblkno'表示要为其查找父级的子页面。'level'是
 * 子页面的级别。进入时，*parentblkno和*downlinkoffnum可以
 * 指向下行链接曾经所在的位置 - 我们将首先检查该
 * 位置，如果没有移动，可以节省一些周期。该函数
 * 返回一个包含下行链接的缓冲区，独占锁定，并且
 * *parentblkno和*downlinkoffnum被设置为下行链接的实际位置。
 *
 * 如果子页面是叶子（level == 0），调用者必须提供一个正确的
 * parentblkno。否则，我们使用父映射哈希表来查找父块。
 *
 * 这个函数在正常索引插入过程中与gistFindCorrectParent()具有相同的目的，
 * 但由于我们不需要处理并发插入，这个更简单。
 */
static Buffer fc_gistBufferingFindCorrectParent(GISTBuildState *fc_buildstate,
							   BlockNumber fc_childblkno, int fc_level,
							   BlockNumber *fc_parentblkno,
							   OffsetNumber *fc_downlinkoffnum)
{
	BlockNumber fc_parent;
	Buffer		fc_buffer;
	Page		fc_page;
	OffsetNumber fc_maxoff;
	OffsetNumber fc_off;

	if (fc_level > 0)
		fc_parent = fc_gistGetParent(fc_buildstate, fc_childblkno);
	else
	{
		/*
		 * 对于叶子页面，调用者必须提供一个正确的父块
		 * 编号。
		 */
		if (*fc_parentblkno == InvalidBlockNumber)
			elog(ERROR, "no parent buffer provided of child %u", fc_childblkno);
		fc_parent = *fc_parentblkno;
	}

	fc_buffer = ReadBuffer(fc_buildstate->indexrel, fc_parent);
	fc_page = BufferGetPage(fc_buffer);
	LockBuffer(fc_buffer, GIST_EXCLUSIVE);
	gistcheckpage(fc_buildstate->indexrel, fc_buffer);
	fc_maxoff = PageGetMaxOffsetNumber(fc_page);

	/* 检查它是否没有移动 */
	if (fc_parent == *fc_parentblkno && *fc_parentblkno != InvalidBlockNumber &&
		*fc_downlinkoffnum != InvalidOffsetNumber && *fc_downlinkoffnum <= fc_maxoff)
	{
		ItemId		fc_iid = PageGetItemId(fc_page, *fc_downlinkoffnum);
		IndexTuple	fc_idxtuple = (IndexTuple) PageGetItem(fc_page, fc_iid);

		if (ItemPointerGetBlockNumber(&(fc_idxtuple->t_tid)) == fc_childblkno)
		{
			/* 仍然在这里 */
			return fc_buffer;
		}
	}

	/*
	 * 下行链接不在以前的位置。扫描页面以
	 * 查找它。在正常的gist插入过程中，它可能已移动到另一个
	 * 页面，向右，但在缓冲构建过程中，我们在查找表中跟踪每个页面的
	 * 父级，因此我们应该始终知道它在什么页面上。
	 */
	for (fc_off = FirstOffsetNumber; fc_off <= fc_maxoff; fc_off = OffsetNumberNext(fc_off))
	{
		ItemId		fc_iid = PageGetItemId(fc_page, fc_off);
		IndexTuple	fc_idxtuple = (IndexTuple) PageGetItem(fc_page, fc_iid);

		if (ItemPointerGetBlockNumber(&(fc_idxtuple->t_tid)) == fc_childblkno)
		{
			/* 是的！！找到了 */
			*fc_downlinkoffnum = fc_off;
			return fc_buffer;
		}
	}

	elog(ERROR, "failed to re-find parent for block %u", fc_childblkno);
	return InvalidBuffer;		/* 保持编译器安静 */
}

/*
 * 处理缓冲区清空栈。一个缓冲区的清空可能会导致其他缓冲区的清空。
 * 该函数迭代，直到这个级联清空过程结束，例如，直到缓冲区清空栈为空。
 */
static void fc_gistProcessEmptyingQueue(GISTBuildState *fc_buildstate)
{
	GISTBuildBuffers *fc_gfbb = fc_buildstate->gfbb;

	/* 当我们在缓冲区清空栈中有元素时迭代。 */
	while (fc_gfbb->bufferEmptyingQueue != NIL)
	{
		GISTNodeBuffer *fc_emptyingNodeBuffer;

		/* 从清空栈中获取节点缓冲区。 */
		fc_emptyingNodeBuffer = (GISTNodeBuffer *) linitial(fc_gfbb->bufferEmptyingQueue);
		fc_gfbb->bufferEmptyingQueue = list_delete_first(fc_gfbb->bufferEmptyingQueue);
		fc_emptyingNodeBuffer->queuedForEmptying = false;

		/*
		 * 我们要加载将要为空的缓冲区的最后页面。
		 * 所以让我们卸载任何先前加载的缓冲区。
		 */
		gistUnloadNodeBuffers(fc_gfbb);

		/*
		 * 从缓冲区中弹出元组，并将它们传递到
		 * 较低级别的缓冲区或叶子页面。我们继续，直到其中一个
		 * 较低级别的缓冲区填满，或者这个缓冲区为空。
		 *
		 * 在Arge等人的论文中，缓冲区清空在处理1/2节点缓冲区数量的元组后停止，
		 * 以避免过度填充任何较低级别的缓冲区。然而，继续进行直到其中一个
		 * 较低级别的缓冲区实际填满更为高效，因此我们这样做。
		 * 这不需要精确，如果一个缓冲区多填了一些元组，也没有伤害。
		 */
		while (true)
		{
			IndexTuple	fc_itup;

			/* 从缓冲区获取下一个索引元组 */
			if (!gistPopItupFromNodeBuffer(fc_gfbb, fc_emptyingNodeBuffer, &fc_itup))
				break;

			/*
			 * 将其运行到底层节点缓冲区或叶页。
			 *
			 * 注意：我们正在清空的缓冲区可能会因为这一调用而分裂。如果发生这种情况，我们的emptyingNodeBuffer指向分裂的左半部分。分裂后，新左缓冲区很可能不再超过半满阈值，但我们最好继续从中刷新元组，直到填满一个下级缓冲区。
			 */
			if (fc_gistProcessItup(fc_buildstate, fc_itup, fc_emptyingNodeBuffer->nodeBlocknum, fc_emptyingNodeBuffer->level))
			{
				/*
				 * 下级缓冲区已满。停止清空此缓冲区，以避免下级缓冲区溢出。
				 */
				break;
			}

			/* 释放在索引元组处理期间分配的所有内存 */
			MemoryContextReset(fc_buildstate->giststate->tempCxt);
		}
	}
}

/*
 * 从顶部到底部清空所有节点缓冲区。这是在索引构建结束时进行的，以将所有剩余元组刷新到索引中。
 *
 * 注意：这会销毁buffersOnLevels列表，因此在此调用后不应再插入缓冲区。
 */
static void fc_gistEmptyAllBuffers(GISTBuildState *fc_buildstate)
{
	GISTBuildBuffers *fc_gfbb = fc_buildstate->gfbb;
	MemoryContext fc_oldCtx;
	int			fc_i;

	fc_oldCtx = MemoryContextSwitchTo(fc_buildstate->giststate->tempCxt);

	/*
	 * 从上到下遍历各个层级。
	 */
	for (fc_i = fc_gfbb->buffersOnLevelsLen - 1; fc_i >= 0; fc_i--)
	{
		/*
		 * 清空此层级上的所有缓冲区。请注意，在处理过程中，由于页面分裂，列表中可能会出现新的缓冲区，因此简单遍历列表是行不通的。当我们看到缓冲区为空时，会将其从列表中移除；一旦完全清空，缓冲区就不能再变为非空。
		 */
		while (fc_gfbb->buffersOnLevels[fc_i] != NIL)
		{
			GISTNodeBuffer *fc_nodeBuffer;

			fc_nodeBuffer = (GISTNodeBuffer *) linitial(fc_gfbb->buffersOnLevels[fc_i]);

			if (fc_nodeBuffer->blocksCount != 0)
			{
				/*
				 * 将此缓冲区添加到清空队列，并继续清空队列。
				 */
				if (!fc_nodeBuffer->queuedForEmptying)
				{
					MemoryContextSwitchTo(fc_gfbb->context);
					fc_nodeBuffer->queuedForEmptying = true;
					fc_gfbb->bufferEmptyingQueue =
						lcons(fc_nodeBuffer, fc_gfbb->bufferEmptyingQueue);
					MemoryContextSwitchTo(fc_buildstate->giststate->tempCxt);
				}
				fc_gistProcessEmptyingQueue(fc_buildstate);
			}
			else
				fc_gfbb->buffersOnLevels[fc_i] =
					list_delete_first(fc_gfbb->buffersOnLevels[fc_i]);
		}
		elog(DEBUG2, "emptied all buffers at level %d", fc_i);
	}
	MemoryContextSwitchTo(fc_oldCtx);
}

/*
 * 获取GiST索引的深度。
 */
static int fc_gistGetMaxLevel(Relation fc_index)
{
	int			fc_maxLevel;
	BlockNumber fc_blkno;

	/*
	 * 从根节点开始向下遍历树，直到达到叶子层级。
	 */
	fc_maxLevel = 0;
	fc_blkno = GIST_ROOT_BLKNO;
	while (true)
	{
		Buffer		fc_buffer;
		Page		fc_page;
		IndexTuple	fc_itup;

		fc_buffer = ReadBuffer(fc_index, fc_blkno);

		/*
		 * 在索引构建期间没有并发访问，因此锁定只是形式上的。
		 */
		LockBuffer(fc_buffer, GIST_SHARE);
		fc_page = (Page) BufferGetPage(fc_buffer);

		if (GistPageIsLeaf(fc_page))
		{
			/* 我们到达底部，工作完成。 */
			UnlockReleaseBuffer(fc_buffer);
			break;
		}

		/*
		 * 选择页面上的第一个下行链接，并跟随它。选择哪个下行链接并不重要，树在各处的深度都是相同的，因此我们只需选择第一个。
		 */
		fc_itup = (IndexTuple) PageGetItem(fc_page,
										PageGetItemId(fc_page, FirstOffsetNumber));
		fc_blkno = ItemPointerGetBlockNumber(&(fc_itup->t_tid));
		UnlockReleaseBuffer(fc_buffer);

		/*
		 * 我们正在向树中向下移动。这意味着树中还有一个层级。
		 */
		fc_maxLevel++;
	}
	return fc_maxLevel;
}


/*
 * 管理父映射的例程。
 *
 * 每当页面被拆分时，我们需要将下行链接插入到父级中。
 * 我们需要以某种方式找到父页面来执行此操作。在正常插入中，
 * 我们在下降树时保持一个访问节点的栈。然而，在缓冲构建中，
 * 我们可以从任何内部节点开始下降树，
 * 当我们通过 cascading tuples 清空一个缓冲区时。因此，在那时我们并没有
 * 可用的完整栈直至根节点。
 *
 * 因此，我们维护一个哈希表来跟踪每个内部页面的父级。
 * 不过，我们不需要跟踪叶子节点的父级。每当
 * 我们插入到一个叶子时，我们刚刚从其父节点下降，因此我们已经知道
 * 它的直接父节点。这大大帮助限制了此哈希表的内存使用。
 *
 * 每当一个内部节点被拆分时，父映射需要更新。
 * 新子页面的父级需要被记录，并且所有在拆分时其下行链接
 * 被移动到新页面的页面的条目也需要更新。
 *
 * 每当我们下降树时，我们也更新父映射。那看起来似乎
 * 不必要，因为每当下行链接被移动或创建时我们保持映射，
 * 但这是必需的，因为在用常规索引插入创建树后我们切换到缓冲模式。
 * 在切换到缓冲模式之前创建的任何页面在最初将不会出现在父映射中，
 * 但在我们第一次访问它们时将被添加进去。
 */

typedef struct
{
	BlockNumber childblkno;		/* 哈希键 */
	BlockNumber parentblkno;
} ParentMapEntry;

static void fc_gistInitParentMap(GISTBuildState *fc_buildstate)
{
	HASHCTL		fc_hashCtl;

	fc_hashCtl.keysize = sizeof(BlockNumber);
	fc_hashCtl.entrysize = sizeof(ParentMapEntry);
	fc_hashCtl.hcxt = CurrentMemoryContext;
	fc_buildstate->parentMap = hash_create("gistbuild parent map",
										1024,
										&fc_hashCtl,
										HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
}

static void fc_gistMemorizeParent(GISTBuildState *fc_buildstate, BlockNumber fc_child, BlockNumber fc_parent)
{
	ParentMapEntry *fc_entry;
	bool		fc_found;

	fc_entry = (ParentMapEntry *) hash_search(fc_buildstate->parentMap,
										   (const void *) &fc_child,
										   HASH_ENTER,
										   &fc_found);
	fc_entry->parentblkno = fc_parent;
}

/*
 * 扫描页面上的所有下行链接，并记住它们的父级。
 */
static void fc_gistMemorizeAllDownlinks(GISTBuildState *fc_buildstate, Buffer fc_parentbuf)
{
	OffsetNumber fc_maxoff;
	OffsetNumber fc_off;
	BlockNumber fc_parentblkno = BufferGetBlockNumber(fc_parentbuf);
	Page		fc_page = BufferGetPage(fc_parentbuf);

	Assert(!GistPageIsLeaf(fc_page));

	fc_maxoff = PageGetMaxOffsetNumber(fc_page);
	for (fc_off = FirstOffsetNumber; fc_off <= fc_maxoff; fc_off++)
	{
		ItemId		fc_iid = PageGetItemId(fc_page, fc_off);
		IndexTuple	fc_idxtuple = (IndexTuple) PageGetItem(fc_page, fc_iid);
		BlockNumber fc_childblkno = ItemPointerGetBlockNumber(&(fc_idxtuple->t_tid));

		fc_gistMemorizeParent(fc_buildstate, fc_childblkno, fc_parentblkno);
	}
}

static BlockNumber fc_gistGetParent(GISTBuildState *fc_buildstate, BlockNumber fc_child)
{
	ParentMapEntry *fc_entry;
	bool		fc_found;

	/* 在哈希表中查找节点缓冲区 */
	fc_entry = (ParentMapEntry *) hash_search(fc_buildstate->parentMap,
										   (const void *) &fc_child,
										   HASH_FIND,
										   &fc_found);
	if (!fc_found)
		elog(ERROR, "could not find parent of block %u in lookup table", fc_child);

	return fc_entry->parentblkno;
}
